Abstract: To find out the shortest paths from a single source to all other vertices’s is a common problem in graph analysis. The Bellman¬Ford’s algorithm is solves such a single¬source shortestpath (SSSP) problem and better applies to beparallelized for many¬core architectures. TheSequential Bellman-Ford Algorithm is that it very time consuming for large data set & it's time complexity is O(ve). Therefore, frontier based Bellman¬Ford's algorithm significantly reduces the number of relaxation operation, number of iterations and time required for search task. This paper presents a parallel implementation of the Bellman¬Ford algorithm based on frontier propagation. General Purpose Graphics Processing Units (GPGPU) based parallel computing is the best alternate way to speed up the search task. This paper gives detailed information about frontier based Bellman¬Ford's algorithm to solve optimization problem & improve the performance of GPU based computing.

Keywords: Bellman­Ford, SSSP, GPGPU, Parallel graph algorithms.